home *** CD-ROM | disk | FTP | other *** search
/ Enigma Amiga Life 109 / EnigmaAmiga109CD.iso / dalla rivista / host contacted / jikes.lha / jikes-1.11 / src / tuple.h < prev    next >
C/C++ Source or Header  |  2000-01-16  |  13KB  |  475 lines
  1. // $Id: tuple.h,v 1.7 1999/10/15 02:30:42 shields Exp $
  2. //
  3. // This software is subject to the terms of the IBM Jikes Compiler
  4. // License Agreement available at the following URL:
  5. // http://www.ibm.com/research/jikes.
  6. // Copyright (C) 1996, 1998, International Business Machines Corporation
  7. // and others.  All Rights Reserved.
  8. // You must accept the terms of that agreement to use this software.
  9. //
  10. #ifndef TUPLE_INCLUDED
  11. #define TUPLE_INCLUDED
  12.  
  13. #ifdef WIN32_FILE_SYSTEM
  14. #include <windows.h>
  15. #endif
  16.  
  17. #include "config.h"
  18. #include <string.h>
  19. #include <stdlib.h>
  20. #include <stdio.h>
  21. #include <assert.h>
  22.  
  23. class OutputBuffer;
  24.  
  25. //
  26. // This Tuple template class can be used to construct a dynamic
  27. // array of arbitrary objects. The space for the array is allocated in
  28. // blocks of size 2**LOG_BLKSIZE. In declaring a tuple the user
  29. // may specify an estimate of how many elements he expects.
  30. // Based on that estimate, suitable value will be calsulated log_blksize
  31. // and base_increment. If these estimates are off, more space will be
  32. // allocated.
  33. //
  34. template <class T>
  35. class Tuple
  36. {
  37. protected:
  38.  
  39.     friend class OutputBuffer;
  40.  
  41.     enum { DEFAULT_LOG_BLKSIZE = 3, DEFAULT_BASE_INCREMENT = 4 };
  42.  
  43.     T **base;
  44.     int base_size,
  45.         top,
  46.         size;
  47.  
  48.     int log_blksize,
  49.         base_increment;
  50.  
  51.     inline int Blksize() { return (1 << log_blksize); }
  52.  
  53.     //
  54.     // Allocate another block of storage for the dynamic array.
  55.     //
  56.     inline void AllocateMoreSpace()
  57.     {
  58.         //
  59.         // The variable size always indicates the maximum number of
  60.         // elements that has been allocated for the array.
  61.         // Initially, it is set to 0 to indicate that the array is empty.
  62.         // The pool of available elements is divided into segments of size
  63.         // 2**log_blksize each. Each segment is pointed to by a slot in
  64.         // the array base.
  65.         //
  66.         // By dividing size by the size of the segment we obtain the
  67.         // index for the next segment in base. If base is full, it is
  68.         // reallocated.
  69.         //
  70.         //
  71.         int k = size >> log_blksize; /* which segment? */
  72.  
  73.         //
  74.         // If the base is overflowed, reallocate it and initialize the new elements to NULL.
  75.         //
  76.         if (k == base_size)
  77.         {
  78.             int old_base_size = base_size;
  79.             T **old_base = base;
  80.  
  81.             base_size += base_increment;
  82.             base = new T*[base_size];
  83.  
  84.             if (old_base != NULL)
  85.             {
  86.                 memmove(base, old_base, old_base_size * sizeof(T *));
  87.                 delete [] old_base;
  88.             }
  89.             memset(&base[old_base_size], 0, (base_size - old_base_size) * sizeof(T *));
  90.         }
  91.  
  92.         //
  93.         // We allocate a new segment and place its adjusted address in
  94.         // base[k]. The adjustment allows us to index the segment directly,
  95.         // instead of having to perform a subtraction for each reference.
  96.         // See operator[] below.
  97.         //
  98.         base[k] = new T[Blksize()];
  99.         base[k] -= size;
  100.  
  101.         //
  102.         // Finally, we update SIZE.
  103.         //
  104.         size += Blksize();
  105.  
  106.         return;
  107.     }
  108.  
  109. public:
  110.  
  111.     //
  112.     // This function is invoked with an integer argument n. It ensures
  113.     // that enough space is allocated for n elements in the dynamic array.
  114.     // I.e., that the array will be indexable in the range  (0..n-1)
  115.     //
  116.     // Note that this function can be used as a garbage collector.  When
  117.     // invoked with no argument(or 0), it frees up all dynamic space that
  118.     // was allocated for the array.
  119.     //
  120.     inline void Resize(const int n = 0)
  121.     {
  122.         //
  123.         // If array did not previously contain enough space, allocate
  124.         // the necessary additional space. Otherwise, if the array had
  125.         // more blocks than are needed, release the extra blocks.
  126.         //
  127.         if (n > size)
  128.         {
  129.             do
  130.             {
  131.                 AllocateMoreSpace();
  132.             } while (n > size);
  133.         }
  134.         else if (n < size)
  135.         {
  136.             // slot is the index of the base element whose block
  137.             // will contain the (n-1)th element.
  138.             int slot = (n <= 0 ? -1 : (n - 1) >> log_blksize);
  139.  
  140.             for (int k = (size >> log_blksize) - 1; k > slot; k--)
  141.             {
  142.                 size -= Blksize();
  143.                 base[k] += size;
  144.                 delete [] base[k];
  145.                 base[k] = NULL;
  146.             }
  147.  
  148.             if (slot < 0)
  149.             {
  150.                 delete [] base;
  151.                 base = NULL;
  152.                 base_size = 0;
  153.             }
  154.         }
  155.  
  156.         top  = n;
  157.     }
  158.  
  159.     //
  160.     // This function is used to reset the size of a dynamic array without
  161.     // allocating or deallocting space. It may be invoked with an integer
  162.     // argument n which indicates the new size or with no argument which
  163.     // indicates that the size should be reset to 0.
  164.     //
  165.     inline void Reset(const int n = 0)
  166.     {
  167.         assert(n >= 0 && n <= size);
  168.  
  169.         top = n;
  170.     }
  171.  
  172.     //
  173.     // Return length of the dynamic array.
  174.     //
  175.     inline int Length() { return top; }
  176.  
  177.     //
  178.     // Return a reference to the ith element of the dynamic array.
  179.     //
  180.     // Note that no check is made here to ensure that 0 <= i < top.
  181.     // Such a check might be useful for debugging and a range exception
  182.     // should be thrown if it yields true.
  183.     //
  184.     inline T& operator[](const int i)
  185.     {
  186.         assert(i >= 0 && i < top);
  187.  
  188.         return base[i >> log_blksize][i];
  189.     }
  190.  
  191.     //
  192.     // Add an element to the dynamic array and return the top index.
  193.     //
  194.     inline int NextIndex()
  195.     {
  196.         int i = top++;
  197.         if (i == size)
  198.             AllocateMoreSpace();
  199.         return i;
  200.     }
  201.  
  202.     inline void Push(T elt) { this -> Next() = elt; }
  203.     // Not "return (*this)[--top]" because that may violate an invariant
  204.     // in operator[].
  205.     inline T Pop() { assert(top!=0); top--; return base[top >> log_blksize][top]; }
  206.     inline T Top() { assert(top!=0); return (*this)[top-1]; }
  207.  
  208.     //
  209.     // Add an element to the dynamic array and return a reference to
  210.     // that new element.
  211.     //
  212.     inline T& Next() { int i = NextIndex(); return base[i >> log_blksize][i]; }
  213.  
  214.     //
  215.     // Assignment of a dynamic array to another.
  216.     //
  217.     inline Tuple<T>& operator=(const Tuple<T>& rhs)
  218.     {
  219.         if (this != &rhs)
  220.         {
  221.             Resize(rhs.top);
  222.             for (int i = 0; i < rhs.top; i++)
  223.                 base[i >> log_blksize][i] = rhs.base[i >> log_blksize][i];
  224.         }
  225.  
  226.         return *this;
  227.     }
  228.  
  229.     //
  230.     // Constructor of a Tuple
  231.     //
  232.     Tuple(unsigned estimate = 0)
  233.     {
  234.         if (estimate == 0)
  235.         {
  236.             log_blksize = DEFAULT_LOG_BLKSIZE;
  237.             base_increment = DEFAULT_BASE_INCREMENT;
  238.         }
  239.         else
  240.         {
  241.             for (log_blksize = 1; (((unsigned) 1 << log_blksize) < estimate) && (log_blksize < 31); log_blksize++)
  242.                 ;
  243.             if (log_blksize <= DEFAULT_LOG_BLKSIZE)
  244.                 base_increment = 1;
  245.             else if (log_blksize < 13)
  246.             {
  247.                 base_increment = (unsigned) 1 << (log_blksize - 4);
  248.                 log_blksize = 4;
  249.             }
  250.             else
  251.             {
  252.                 base_increment = (unsigned) 1 << (log_blksize - 8);
  253.                 log_blksize = 8;
  254.             }
  255.             base_increment++; // add a little margin to avoid reallocating the base.
  256.         }
  257.  
  258.         base_size = 0;
  259.         size = 0;
  260.         top = 0;
  261.         base = NULL;
  262.     }
  263.  
  264.     //
  265.     // Constructor of a Tuple
  266.     //
  267.     Tuple(int log_blksize_, int base_increment_) : log_blksize(log_blksize_),
  268.                                                    base_increment(base_increment_)
  269.     {
  270.         base_size = 0;
  271.         size = 0;
  272.         top = 0;
  273.         base = NULL;
  274.     }
  275.  
  276.     //
  277.     // Initialization of a dynamic array.
  278.     //
  279.     Tuple(const Tuple<T>& rhs) : log_blksize(rhs.log_blksize),
  280.                                  base_increment(rhs.base_increment)
  281.     {
  282.         base_size = 0;
  283.         size = 0;
  284.         base = NULL;
  285.         *this = rhs;
  286.     }
  287.  
  288.     //
  289.     // Destructor of a dynamic array.
  290.     //
  291.     ~Tuple() { Resize(0); }
  292.  
  293.     // ********************************************************************************************** //
  294.  
  295.     //
  296.     // Return the total size of temporary space allocated.
  297.     //
  298.     inline size_t SpaceAllocated(void)
  299.     {
  300.         return ((base_size * sizeof(T **)) + (size * sizeof(T)));
  301.     }
  302.  
  303.     //
  304.     // Return the total size of temporary space used.
  305.     //
  306.     inline size_t SpaceUsed(void)
  307.     {
  308.         return (((size >> log_blksize) * sizeof(T **)) + (top * sizeof(T)));
  309.     }
  310. };
  311.  
  312.  
  313. //
  314. //
  315. //
  316. template <class T>
  317. class ConvertibleArray : public Tuple<T>
  318. {
  319. public:
  320.  
  321.     ConvertibleArray(int estimate = 0) : Tuple<T>(estimate),
  322.                                          array(NULL)
  323.     {}
  324.  
  325.     ConvertibleArray(int log_blksize, int base_increment) : Tuple<T>(log_blksize, base_increment),
  326.                                                             array(NULL)
  327.     {}
  328.  
  329.     ~ConvertibleArray() { delete [] array; }
  330.  
  331.     //
  332.     // This function converts a tuple into a regular array and destroys the
  333.     // original tuple.
  334.     //
  335.     inline T *&Array()
  336.     {
  337.         if ((! array) && Tuple<T>::top > 0)
  338.         {
  339.             array = new T[Tuple<T>::top];
  340.  
  341.             int i = 0,
  342.                 processed_size = 0,
  343.                 n = (Tuple<T>::top - 1) >> Tuple<T>::log_blksize; // the last non-empty slot!
  344.             while (i < n)
  345.             {
  346.                 memmove(&array[processed_size], Tuple<T>::base[i] + processed_size, Tuple<T>::Blksize() * sizeof(T));
  347.                 delete [] (Tuple<T>::base[i] + processed_size);
  348.                 i++;
  349.                 processed_size += Tuple<T>::Blksize();
  350.             }
  351.             memmove(&array[processed_size], Tuple<T>::base[n] + processed_size, (Tuple<T>::top - processed_size) * sizeof(T));
  352.             delete [] (Tuple<T>::base[n] + processed_size);
  353.             delete [] Tuple<T>::base;
  354.             Tuple<T>::base = NULL;
  355.             Tuple<T>::size = 0;
  356.         }
  357.  
  358.         return array;
  359.     }
  360.  
  361.     inline T& operator[](const int i)
  362.     {
  363.         assert(i >= 0 && i < Tuple<T>::top);
  364.  
  365.         return (array ? array[i] : Tuple<T>::base[i >> Tuple<T>::log_blksize][i]);
  366.     }
  367.  
  368.     inline void Resize(const int n = 0) { assert(false); }
  369.     inline void Reset(const int n = 0) { assert(false); }
  370.     inline T& Next()
  371.     {
  372.         assert(! array);
  373.  
  374.         int i = Tuple<T>::NextIndex();
  375.         return Tuple<T>::base[i >> Tuple<T>::log_blksize][i];
  376.     }
  377.     inline Tuple<T>& operator=(const Tuple<T>& rhs)
  378.     {
  379.         assert(false);
  380.         return *this;
  381.     }
  382.  
  383. private:
  384.  
  385.     T *array;
  386. };
  387.  
  388.  
  389. //
  390. //
  391. //
  392. class OutputBuffer
  393. {
  394. public:
  395.  
  396.     OutputBuffer(int log_blksize = 13, int base_increment = 128) : buffer(log_blksize, base_increment) {}
  397.  
  398.     inline void PutB1(u1 u) { buffer.Next() = u; }
  399.  
  400.     inline void PutB2(u2 u)
  401.     {
  402.         buffer.Next() = u >> 8;
  403.         buffer.Next() = u & 0xff;
  404.     }
  405.  
  406.     inline void PutB4(u4 u)
  407.     {
  408.         buffer.Next() = u >> 24;
  409.         buffer.Next() = (u >> 16) & 0xff;
  410.         buffer.Next() = (u >> 8)  & 0xff;
  411.         buffer.Next() = u & 0xff;
  412.     }
  413.  
  414.     inline void put_n(u1 *u, int n)
  415.     {
  416.         for (int i = 0; i < n; i++)
  417.             buffer.Next() = u[i];
  418.     }
  419.  
  420.     inline bool WriteToFile(char *file_name)
  421.     {
  422. #if defined(UNIX_FILE_SYSTEM) || defined(AMIGAOS_FILE_SYSTEM)
  423.         FILE *file = ::SystemFopen(file_name, "wb");
  424.         if (file  ==  (FILE *) NULL)
  425.             return false;
  426.  
  427.         int i = 0,
  428.             size = 0,
  429.             n = (buffer.top - 1) >> buffer.log_blksize; // the last non-empty slot!
  430.         while (i < n)
  431.         {
  432.             fwrite(buffer.base[i] + size, sizeof(u1), buffer.Blksize(), file);
  433.             i++;
  434.             size += buffer.Blksize();
  435.         }
  436.         fwrite(buffer.base[n] + size, sizeof(u1), (buffer.top - size), file);
  437.  
  438.         fclose(file);
  439. #elif defined(WIN32_FILE_SYSTEM)
  440.         HANDLE file = CreateFile(file_name, GENERIC_READ | GENERIC_WRITE, 0, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
  441.         HANDLE mapfile = (file == INVALID_HANDLE_VALUE
  442.                                      ? file
  443.                                      : CreateFileMapping(file, NULL, PAGE_READWRITE, 0, buffer.top, NULL));
  444.         if (mapfile == INVALID_HANDLE_VALUE)
  445.             return false;
  446.         u1 *string_buffer = (u1 *) MapViewOfFile(mapfile, FILE_MAP_WRITE, 0, 0, buffer.top);
  447.  
  448.         assert(string_buffer);
  449.  
  450.         int i = 0,
  451.             size = 0,
  452.             n = (buffer.top - 1) >> buffer.log_blksize; // the last non-empty slot!
  453.         while (i < n)
  454.         {
  455.             memmove(&string_buffer[size], buffer.base[i] + size, buffer.Blksize() * sizeof(u1));
  456.             i++;
  457.             size += buffer.Blksize();
  458.         }
  459.         memmove(&string_buffer[size], buffer.base[n] + size, (buffer.top - size) * sizeof(u1));
  460.  
  461.         UnmapViewOfFile(string_buffer);
  462.         CloseHandle(mapfile);
  463.         CloseHandle(file);
  464. #endif
  465.  
  466.         return true;
  467.     }
  468.  
  469. private:
  470.  
  471.     Tuple<u1> buffer;
  472. };
  473.  
  474. #endif /* #ifndef TUPLE_INCLUDED */
  475.